package BinaryTreePackage;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class middleorderIteration_ {


  public List<Integer> Iteration(TreeNode root){
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;

    while(!stack.isEmpty() || node != null){
      if (node != null){
        stack.push(node);
        node = node.left;
      }else{
        node = stack.pop();
        result.add(node.val);
        node = node.right;
      }
    }

    return result;
  }
}
